The present invention generally relates to a method and apparatus to improve the appearance of images produced by an output device. More particularly, the present invention is directed to a method and device for performing multi-level error diffusion using semi-vector quantization.
Error diffusion is a well known technique of processing image data that attempts to maintain the total intensity or gray content of an image when converting an image comprising pixels having one set of gray levels to an image comprising pixels having a different set of gray levels. For example, when reducing continuous tone (contone) image data to one of Nxe2x89xa72 discrete gray levels, contone data having a gray value falling between the discrete gray levels are often assigned or quantized to the closest gray level, although the algorithm may always assign such intermediate gray values to the next highest (or lowest) gray level. The inherent error resulting from such a choice is propagated in specified amounts to adjacent picture elements or pixels not yet processed. That is, the error in the intensity of the image is diffused and, on average, zero.
The fraction of the error added to each neighbor depends on a set of weights, the total error being multiplied by the weight corresponding to a given neighbor and then added to the value of that neighbor. The choice of weights can greatly affect the image quality, and much has been said about weights appropriate for giving pleasing results. A more complete discussion of error diffusion and weighting coefficients can be found in the following references which are incorporated by reference herein for their teachings: U.S. Pat. No. 5,353,127, entitled xe2x80x9cMethod For Quantization Gray Level Pixel Data With Extended Distribution Setxe2x80x9d to Shiau et al.; U.S. Pat. No. 5,608,821 entitled xe2x80x9cMethod Of High Addressability Error Diffusionxe2x80x9d to Metcalfe et al.; U.S. Pat. No. 5,696,601 entitled xe2x80x9cSystem And Method For Redistributing Error Values From An Error Diffusion Processxe2x80x9d to Metcalfe et al.; and U.S. Pat. No. 5,768,432 entitled xe2x80x9cSystem And Apparatus For Pixel Growth Compensation In A Hybrid Error Diffusion Processxe2x80x9d to Schweid. It should be appreciated that the references cited above are but a small sample of the available error diffusion techniques known in the art and that the present invention is not meant to be limited to the diffusion techniques shown therein.
In the case of color images, error diffusion cannot simply be applied to each color component independently. To do so would produce noisy images. For example, a light blue can be produced by magenta and cyan pixels. But if the magenta and cyan are processed independently, then some pixels may have both magenta and cyan, yielding blue, while others have no ink at all, giving white. This mixture of white, blue, magenta and cyan will have more contrast and look noisier than pixels of magenta and cyan alone. The process of independently processing each channel can result in any and all of the eight possible pixel colors distributed over an image area. The problem of image noisiness can be reduced by the method of vector error diffusion. In this scheme the color chosen for each pixel is the color in a selected color space closest to the desired value, where the desired value is the input value modified by the errors diffused from neighboring pixels. This tends to confine the pixel colors to a subset near the input value and reduces the noise. What is known as vector error diffusion was described in a paper by Venable et al., xe2x80x9cSelection and Use of Small Color Sets for Pictorial Displayxe2x80x9d, Proc ISandT Annual Meeting, Rochester, 1990 and in a paper by Miller et al. xe2x80x9cColor Halftoning Using Error Diffusion and a Human Visual System Modelxe2x80x9d, Proc ISandT Annual Meeting, Rochester, 1990. In vector error diffusion colors are treated as points in a three dimensional space, with the colors printable or displayable at a given pixel discrete locations within that space. When a continuous tone color is to be displayed, the closest displayable or printable color is selected, and the error (the difference between the input color and added error, and the output color) is calculated as a vector in color space. Here, the xe2x80x9cclosenessxe2x80x9d might be the simple distance in color space or a weighted distance based on the human visual model. The vector is the difference between the desired color and the available color. The (vector) error is then diffused in the same way as in normal error diffusion.
There are, however, some problems with vector error diffusion. One is the difficult three dimensional computation required to find the closest color at each pixel. Another problem with some implementations of vector error diffusion is that the method may still not select the optimal set of colors. For example, it may produce a gray from white and black pixels, where a smoother image might be produced if cyan, magenta and yellow were used because there would be less luminance contrast.
The following references may be relevant to various aspects of the present invention.
U.S. Pat. No. 6,072,591, entitled xe2x80x9cSum and Difference Error Diffusionxe2x80x9d to Harrington and assigned to the same assignee as the present invention, teaches a method for color error diffusion wherein the sum of the three components determines whether a pixel should be black, white or colored. The differences between the components determine whether the pixel should be a primary color, a secondary color or black.
U.S. Pat. No. 5,621,546 suggests performing the error diffusion in two steps. Initially, a simple error diffusion performed on the sum of the requested colorant amounts to indicate when color is needed but not which color is selected. The pixel color is chosen using a vector error diffusion process.
U.S. Pat. No. 5,565,994 teaches multiples separation error diffusion with cross separation correlation control for color images. Each separation of the image is separately processed with an error diffusion process which takes into account the processing of another separation, if any. Output signals from a separation are used to determine threshold values for at least one other separation. The varying thresholds are used to vary the likelihood of the current pixel being a spot or no spot.
U.S. Pat. No. 6,014,233 teaches a method for color error diffusion using semi-vector quantization for three color separations wherein the two separations with the most visually perceptive color output are compared with one another to determine their output colors, while the third, least visually perceptive separation, is treated separately. A correction term may be applied to the third separation based on the color output of the first two separations to insure uniformity of ink coverage.
The references cited herein are incorporated by reference for their teachings.
One aspect of the present invention is a system for processing color image data comprising multiple color separations, each separation including an array of separation pixels each separation pixel having one of L levels. The system includes two diffusion processors. The first diffusion processor receives a first separation pixel from a first color separation and a second separation pixel from a second color separation and derives a multi-level output value for each of the first and second separation pixels based on a sum and a difference of the first and second separation pixels, the multi-level output values for the first and second separation pixels each being one of k levels wherein1 less than k less than L. The second diffusion processor receives a third separation pixel from a third color separation and generates a multi-level output value for the third separation pixel.
Another aspect of the present invention includes a multi-level error diffusion method. The method includes receiving color image data comprising a plurality of color separations, each color separation including an array of separation pixels, each separation pixel having one of L values; generating a sum S of a first separation pixel and a second separation pixel, the first separation pixel being from a first color separation and the second separation pixel from a second color separation; generating a difference D between the first and second separation pixels; deriving a first multi-level output value for the first separation pixel and a second multi-level output value for the second separation pixel from the sum S and the difference D, the first and second multi-level output values each being one of k values wherein1 less than k less than L; and generating a third multi-level output value for a third separation pixel from a third color separation within the color image data.